import org.junit.Test;

import java.util.Arrays;

public class DataStructure {
    //两数之和
    @Test
    public void test1() {
        int[] ints = new int[]{3, 2, 4};
        int target = 6;
        int[] nums = new int[ints.length - 1];
        int count = 0;
        for (int i = 0; i < ints.length - 1; i++) {
            for (int k = i; k < ints.length; k++) {
                if (k != i) {
                    if (ints[k] + ints[i] == target) {
                        nums[count] = i;
                        count++;
                        nums[count] = k;
                        count++;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    //回文数
    @Test
    public void test2() {
        int x = -1;
        int i = x;
        int b = 0;
        while (x > 0) {
            b = b * 10 + x % 10;
            x = x / 10;
        }
        System.out.println(b);
        System.out.println(String.format("%d回文数判断%b", i, i == b));
    }

    //最长公共前缀
    @Test
    public void test3() {
        String[] strs = new String[]{"aaa", "aa", "aaa"};
        String str = strs[0];
        for (String s : strs) {
            int i = 0;
            for (; i < s.length(); i++) {
                if (i >= str.length() || s.charAt(i) != str.charAt(i)) {
                    break;
                }
            }
            str = str.substring(0, i);
        }
        System.out.println(str);
    }

    //删除有序数组中的重复项
    @Test
    public void test4() {
        int[] nums = new int[]{1, 1, 2};
        int count = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[count] < nums[i]) {
                nums[++count] = nums[i];
            }
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(++count);
    }

    //移除元素
    @Test
    public void test5() {
        int[] nums = new int[]{3, 2, 2, 3};
        int val = 3;
        int count = 0;
        /*for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                int s = nums[count];
                nums[count] = nums[i];
                nums[i] = s;
                count ++;
            }
        }*/
        for (int i : nums) {
            if (i != val) {
                nums[count] = i;
                count++;
            }
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(count);
    }

    //搜索插入位置
    @Test
    public void test6() {
        int[] nums = new int[]{1, 3, 5, 6};
        int target = 2;
        //一重循环时间复杂度O(n)
        int i = 0;
        for (; i <= nums.length; i++) {
            if (i == nums.length || nums[i] == target || nums[i] > target) {
                break;
            }
        }
        //二分查找时间复杂度O(logn)
        int left = 0;//左边
        int right = nums.length - 1; //右边
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                break;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(left);
    }

    //最后一个单词的长度
    @Test
    public void test7() {
        String s = "   fly me   to   the moon  ";
        char[] chars = s.toCharArray();
        int count = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == ' ') {
                if (count > 0) {
                    System.out.println(count);
                    break;
                }
                continue;
            }
            count++;
        }
    }

    //加一
    @Test
    public void test8() {
        int digits[] = new int[]{9, 9, 9};
        /*int num = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] + num >= 10) {
                digits[i] = 0;
            } else {
                digits[i] = digits[i] + num;
                num = 0;
                break;
            }
        }
        if (num > 0) {
            int nums[] = new int[digits.length + 1];
            nums[0] = num;
            int count = 1;
            for (int i : digits) {
                nums[count] = i;
                count++;
            }
            System.out.println(Arrays.toString(nums));
        } else {
            System.out.println(Arrays.toString(digits));
        }*/
        int length = digits.length;
        for (int i = length - 1; i >= 0; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i] += 1;
                break;
            }
        }
        if (digits[0] == 0) {
            digits = new int[++length];
            digits[0] = 1;
        }
        System.out.println(Arrays.toString(digits));
    }
}
